/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 */
//汉诺塔问题
public class HanoiTower {
    //一个盘：A->C   (1---2^1-1)
    //2:A->B,A->C,B->C  (3---2^2-1)
    //3:A->C,A->B,C->B,A->C,B->A,B->C,A->C  (7---2^3-1)
    /**
     * 表示从pos1移动到pos2位置
     * @param pos1
     * @param pos2
     */
    public static void move(char pos1,char pos2){
        System.out.print(pos1+"->"+pos2+" ");
    }
    /**
     *
     * @param n  盘子个数
     * @param p1 起始位置
     * @param p2 中途位置
     * @param p3 目标位置
     */
    public  static void hanoi(int n, char pos1,char pos2,char pos3){
        if (n == 1) {//只有一个盘子时候从pos1移动到pos3（起始位置一定到目的位置）
            move(pos1,pos3);
        }else{
            hanoi(n-1,pos1,pos3,pos2);//将第n个盘子上面的n-1个盘子，从pos1移动到pos2（递归）
            move(pos1,pos3);//将第n盘子（最后一个）从pos1移动到pos3
            hanoi(n-1,pos2,pos1,pos3);//将剩余的n-1个盘子依次递归
        }
    }
    public static void main(String[] args) {
        hanoi(3,'A','B','C');
    }
}
